package com.future;

import java.util.Arrays;

/**
 * Description:
 * 给你一个整数数组 nums 和一个目标值 goal 。
 * <p>
 * 你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。
 * <p>
 * 返回 abs(sum - goal) 可能的 最小值 。
 * <p>
 * 注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [5,-7,3,5], goal = 6
 * 输出：0
 * 解释：选择整个数组作为选出的子序列，元素和为 6 。
 * 子序列和与目标值相等，所以绝对差为 0 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/closest-subsequence-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/20:17:25
 */
public class Solution_minAbsDifference_1755 {

    public static void main(String[] args) {

        int maxLength = 10;
        int maxVal = 1000;
        int testTimes = 100;
        int maxGoal = 1_000;
        System.out.println("test start");
        for (int i = 0; i < testTimes; i++) {
            System.out.println("运行第" + i + "个");
            int[] nums = generateRandomArr(maxLength, maxVal);
            int goal = (int) ((1 + maxGoal) * Math.random());
            int a1 = minAbsDifference(nums, goal);
            int a2 = minAbsDifference_2(nums, goal);
            if (a2 != a1) {
                System.out.println("nums=" + Arrays.toString(nums));
                System.out.println("goal=" + goal);
                System.out.println("real ans=" + a1);
                System.out.println("my ans=" + a2);
                throw new RuntimeException();
            }
        }
        System.out.println("test finished");
        int[] nums = {5, -7, 3, 5};
        int goal = 6;
        nums = new int[]{7, -9, 15, -2};
        goal = -5;
        System.out.println(minAbsDifference(nums, goal));
        System.out.println(minAbsDifference_2(nums, goal));

    }


    private static int[] generateRandomArr(int maxLength, int maxVal) {
        int reaLength = (int) ((maxLength + 1) * Math.random());
        int[] arr = new int[reaLength];
        for (int i = 0; i < reaLength; i++) {
            arr[i] = (int) ((maxVal + 1) * Math.random());
        }
        return arr;
    }

    /**
     * 分治
     *
     * @param nums
     * @param goal
     * @return
     */
    public static int minAbsDifference_2(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        int ans = Integer.MAX_VALUE;
        int[] leftHalfArr = new int[1 << 20];
        int[] rightHalfArr = new int[1 << 20];
        int realLIndex = process_2(nums, 0, nums.length >> 1, 0, 0, leftHalfArr);
        int realRIndex = process_2(nums, nums.length >> 1, nums.length, 0, 0, rightHalfArr);
        Arrays.sort(leftHalfArr, 0, realLIndex);
        Arrays.sort(rightHalfArr, 0, realLIndex);
        for (int i = 0; i < realLIndex; i++) {
            int rest = goal - leftHalfArr[i];
            int lIndex = 0;
            while (lIndex < realRIndex) {
                int v1 = Math.abs(rest - rightHalfArr[lIndex]);
                ans = Math.min(ans, v1);
                lIndex++;
            }
        }
        return ans;
    }

    private static int process_2(int[] nums, int curIndex, int end, int reaIndex, int sum, int[] leftHalfArr) {
        if (curIndex == end) {
            leftHalfArr[reaIndex++] = sum;
        } else {
            reaIndex = process_2(nums, curIndex + 1, end, reaIndex, sum, leftHalfArr);
            reaIndex = process_2(nums, curIndex + 1, end, reaIndex, sum + nums[curIndex], leftHalfArr);
        }
        return reaIndex;
    }

    /**
     * 暴力方法
     *
     * @param nums
     * @param goal
     * @return
     */
    public static int minAbsDifference(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        int ans = process(nums, 0, goal);

        return ans;
    }

    private static int process(int[] nums, int index, int rest) {
        if (index == nums.length) {
            return Math.abs(rest);
        }
        int v1 = process(nums, index + 1, rest);
        int v2 = process(nums, index + 1, rest - nums[index]);
        return Math.min(v1, v2);
    }

}
